#include <stdio.h>
#define MaxSize 100
typedef int KeyType;
typedef char ElemType;
typedef struct {
    KeyType key;	//存放关键字,KeyType为关键字类型
    ElemType data;	//其他数据,ElemType为其他数据的类型
} SqType;

#include "sort_base.cpp"	//包含排序基础工具

void SelectSort(SqType R[], int n) {
    int i, j, k;
    SqType tmp;
    for (i = 0; i < n - 1; i++) {
        k = i;
        for (j = i + 1; j < n; j++)
            if (R[j].key < R[k].key)
                k = j;	//用k指出每趟在无序区段的最小元素
        if (k != i) {
            tmp = R[i];	//将R[k]与R[i]交换
            R[i] = R[k];
            R[k] = tmp;
        }
        printf("i=%d: ", i);	//输出一趟排序结果
        for (int a = 0; a < n; a++)
            printf("%3d", R[a].key);
        printf("\n");
    }
}

int find_min(SqType R[], int n, int position) {
    // 在R[position..n-1]中查找最小元素的逻辑序号
    int min_idx = position;
    for (int i = position + 1; i < n; i++)
        if (R[i].key < R[min_idx].key)
            min_idx = i;	//用k指出每趟在无序区段的最小元素
    return min_idx;
}

void select_sort(SqType R[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min_idx = find_min(R, n, i);	//查找最小元素的逻辑序号
        if (min_idx != i) {	//如果最小元素不是当前元素
            //将R[min_idx]与R[i]交换
            swap(R[i], R[min_idx]);
        }
        print_pass(i, R, n);	//输出一趟排序结果
    }
}

int main() {
    SqType R[MaxSize];
    KeyType A[] = {75, 87, 68, 92, 88, 61, 77, 96, 80, 72};
    int i, n = 10;
    for (i = 0; i < n; i++)
        R[i].key = A[i];
    // SelectSort(R, n);

    printf("初始数据: \n");
    print_pass(-1, R, n); // 输出初始数据

    select_sort(R, n);

    printf("排序结果:\n");
    print_pass(99, R, n);


    // printf("排序结果:");
    // for (i = 0; i < n; i++)
    //     printf("%3d", R[i].key);
    // printf("\n");
    return 0;
}
